#include <list>
#include <map>
#include <fstream>
#include "State.cpp"
#include "NFA.h"

using namespace std;

NFA::NFA():
	startState(0)
{
}

NFA::NFA(string filename)
{
	fileName = filename.substr(0, filename.length()-4);
	list<char>* alphabet = new list<char>();
	list<State*> *States = new list<State*>();
	letterPositions = new map<char, int>();
	statePositions = new map<string, int>();
	ifstream ifs;
	ifs.open(filename.c_str());
	string currLine,	//The data holder for our ifstream
		   startStateLine;
	const char  *alphabetLine,
				*acceptChars,
				*stateChars;	
	list<string> *stateLine = new list<string>(),	//The labels held in line 1, in a sorted order
				 *acceptLine = new list<string>();	//The labels held in line 4, in a sorted order


	getline(ifs, currLine);
	//First line: state labels - strings separated by tabs
	stateChars = currLine.c_str();
	string currLabel;
	for(int i = 0; i < currLine.length(); ++i)
	{
		int j = 0;
		while(i + j < currLine.length() && stateChars[i+j] != 9 && stateChars[i+j] != 13)	//9 = \t, 13 = \n
		{	//Move j to the next position which has a delimiter
			j++;
		}
		currLabel = currLine.substr(i,j);
		list<string>::iterator iter, end;
		for(iter = stateLine->begin(),
			end = stateLine->end();
			iter != end && (*iter).compare(currLabel) < 0;
			++iter)
		{
		}	//empty loop, all the logic needed is there already.
		if(iter != end)
		{
			stateLine->insert(iter, currLabel);
		}
		else
		{
			stateLine->push_back(currLabel);
		}
		i += j;	//Make sure this thing stays linear, doesn't loop back over the same characters twice.
	}
	//Make the permanent array from this list of states
	//We won't place the values yet, though, we'll do that when we know if things are accept states.
	numStates = stateLine->size();
	stateArr = new State*[numStates];

	getline(ifs, currLine);
	//Second line: alphabet - single characters, implicitly including EPS (\0)
	alphabet->push_front(EPS);
	alphabetLine = currLine.c_str();
	for(int i = 0; i < currLine.length(); i+=2)
	{	//Every other character will be in the alphabet, the others will be \t or \n.
		alphabet->push_back(alphabetLine[i]);
	}
	numLetters = alphabet->size();
	alphabetArr = new char[numLetters];
	for(int i = 0; i < numLetters; ++i)
	{	//This map will let us go freely between referencing the alphabet by array position vs by letter.
		alphabetArr[i] = alphabet->front();
		letterPositions->insert(pair<char, int>(alphabetArr[i], i));
		alphabet->pop_front();
	}

	//Since we now know how many states and letters there are, we'll create the 2D array[state][letter] for them.
	transitions = new list<int> *[numStates];
	for(int i = 0; i < numStates; ++i)
	{
		transitions[i] = new list<int>[numLetters];
		for(int j = 0; j < numLetters; ++j)
		{
			transitions[i][j] = *(new list<int>());
		}
	}

	getline(ifs, currLine);
	//Third line: starting state
	startStateLine = currLine;

	getline(ifs, currLine);
	//Fourth line: Accept states
	acceptChars = currLine.c_str();
	for(int i = 0; i < currLine.length(); ++i)
	{
		int j = 0;
		while(i + j < currLine.length() && acceptChars[i+j] != 9 && acceptChars[i+j] != 13)	//9 = \t, 13 = \n
		{	//Move j to the next position which has a delimiter
			j++;
		}
		currLabel = currLine.substr(i,j);
		list<string>::iterator iter, end;
		for(iter = acceptLine->begin(),
			end = acceptLine->end();
			iter != end && (*iter).compare(currLabel) < 0;
			++iter)
		{
		}	//empty loop, all the logic needed is there already.
		if(iter != end)
		{
			acceptLine->insert(iter, currLabel);
		}
		else
		{
			acceptLine->push_back(currLabel);
		}
		i += j;	//Make sure this thing stays linear, doesn't loop back over the same characters twice.
	}
	int arrPos = 0;
	while(!stateLine->empty())
	{	//Take the first in-order state label, create a state with it. The state will be labelled as
		State* newState;
		string label = stateLine->front();
		if(label.compare(acceptLine->front()) == 0)
		{	//If the first label in the accept line is the same as the first in the state line, this is an accept state.
			newState = new State(label, true);
			stateLine->pop_front();
			acceptLine->pop_front();
		}
		else
		{	//This is not an accept state.
			newState = new State(label, false);
			stateLine->pop_front();
		}
		if(label.compare(startStateLine) == 0)
		{
			startState = newState;
		}
		statePositions->insert(pair<string, int>(label, arrPos));
		stateArr[arrPos++] = newState;
	}
	//Fifth line on: transition function (each line read as STATELABEL, LETTER = RESULTSTATE
	while(ifs.good())
	{
		getline(ifs, currLine);
		string* transString = splitTransitionLine(currLine);
		int sourcePos = -1, targetPos = -1;
		for(int i = 0; i < numStates; ++i)
		{
			if(stateArr[i]->hasLabel(transString[0]))
			{
				sourcePos = i;
			}
			if(stateArr[i]->hasLabel(transString[2]))
			{
				targetPos = i;
			}
			if(sourcePos >= 0 && targetPos >= 0) break;
		}
		int letterPos;
		if(sourcePos < 0 || targetPos < 0) continue;
		if(transString[1] == "EPS") letterPos = (*(letterPositions->find(EPS))).second;
		else
		{
			char letter = transString[1].c_str()[0];
			letterPos = (*(letterPositions->find(letter))).second;
		}
		transitions[sourcePos][letterPos].push_back(targetPos);
	}
	epsClosures = new State*[numStates];
}

NFA::~NFA()
{
	for(int i = 0; i < numStates; ++i)
	{
		delete stateArr[i];
		stateArr[i] = 0;
		delete transitions[i];
		transitions[i] = 0;
	}
	for(int k = 0; k < numLetters; ++k)
	{
		alphabetArr[k] = 0;
	}
	delete alphabetArr;
	startState = 0;
}

void NFA::addState(list<State*> *states, State* newState)
{
	list<State*>::iterator iter = states->begin(),
						   end = states->end();
	while(iter != end && (*iter)->compareTo(newState) <= 0)
	{
		++iter;
	}
	if(iter!= end)
	{
		states->insert(iter, newState);
	}
	else
	{
		states->push_back(newState);
	}
}

void NFA::setStartState(State* newStart)
{
	startState = newStart;
}

State* NFA::getStartState()
{
	return startState;
}

string NFA::toString()
{
	return "Sup";
}

void NFA::ConvertToDFA()
{
	list<State*>* DFAStates = new list<State*>();
	list<int*>* DFATrans = new list<int*>();
	for(int i = 0; i < numStates; ++i)
	{
		State* thisEps = epsClosure(stateArr[i]);
		bool isInYet = false;
		for(list<State*>::iterator iter = DFAStates->begin(), end = DFAStates->end();
			iter != end; iter++)
		{
			if(thisEps->matches(*iter))
			{
				isInYet = true;
				break;
			}
		}
		if(isInYet) continue;
		DFAStates->push_back(epsClosure(stateArr[i]));
		DFATrans->push_back(new int[numLetters]);
	}
	list<State*>::iterator stateIter = DFAStates->begin(), 
						   stateEnd = DFAStates->end();
	list<int*>::iterator transIter = DFATrans->begin(),
						 transEnd = DFATrans->end();
	while(transIter != transEnd && stateIter != stateEnd)
	{
		int* tempTrans = *transIter;
		State* thisState = *stateIter;
		for(int letterIndex = 1; letterIndex < numLetters; ++letterIndex)	//since Epsilon is special, we'll skip over it. It's always at position 0.
											//We'll be ignoring it when writing out the DFA as well, since DFAs can't have eps
		{
			State* newState = new State();
			for(list<string>::iterator labelIter = thisState->labels->begin(), labelEnd = thisState->labels->end();
				labelIter != labelEnd; labelIter++)
			{
				int statePos = (*(statePositions->find(*labelIter))).second;
				for(list<int>::iterator oldTransIter = transitions[statePos][letterIndex].begin(),
										oldTransEnd = transitions[statePos][letterIndex].end();
										oldTransIter != oldTransEnd; oldTransIter++)
				{
					int newStatePos = *oldTransIter;
					newState->combineWithState(epsClosure(stateArr[newStatePos]));
				}
			}
			int stateIndex = 0;
			bool match = false;
			for(list<State*>::iterator stateIter2 = DFAStates->begin(), stateEnd2 = DFAStates->end(); stateIter2 != stateEnd2 && !match; ++stateIter2)
			{	//Look through our current list of states, see if the new state is already there. If it is, we'll want to set DFATrans for the current position to the found state's position
				//If it isn't in the current list, we add it to the list and point to that.
				if(newState->matches(*stateIter2))
				{
					tempTrans[letterIndex] = stateIndex; 
					match = true;
				}
				++stateIndex;
			}	//stateIndex will now, if match has not been found, be equal to DFAStates->size()
			if(!match)
			{
				tempTrans[letterIndex] = stateIndex;
				DFAStates->push_back(newState);
				DFATrans->push_back(new int[numLetters]);
				stateEnd = DFAStates->end();
				transEnd = DFATrans->end();
			}
		}
		++transIter; 
		++stateIter;
	}
	//Now we'll make the state and transition lists into arrays for quicker access
	int arrayIndex = 0;
	State** DFAStateArr = new State*[DFAStates->size()];
	int** DFATransArr = new int*[DFATrans->size()];
	for(stateIter = DFAStates->begin(), stateEnd = DFAStates->end(), transIter = DFATrans->begin(),
						 transEnd = DFATrans->end();stateIter != stateEnd; ++stateIter)
	{
		DFAStateArr[arrayIndex] = *stateIter;
		DFATransArr[arrayIndex++] = *(transIter++);
	}
	//Everything is now set up for printing out!
	string stateDefLine, startStateLine, acceptStateLine, alphabetLine, transitions;
	alphabetLine = "";
	for(int i = 1; i < numLetters; ++i)
	{
		alphabetLine += alphabetArr[i];
		alphabetLine += "\t";
	}
	startStateLine = epsClosure(startState)->listLabels();
	for(int stateNum = 0; stateNum < DFAStates->size(); ++stateNum)
	{
		if(DFAStateArr[stateNum]->listLabels().compare("EM") != 0)
		{
			stateDefLine += DFAStateArr[stateNum]->listLabels() + "\t";
			if(DFAStateArr[stateNum]->isAcceptState())
			{
				acceptStateLine += DFAStateArr[stateNum]->listLabels() + "\t";
			}
			for(int letter = 1; letter < numLetters; ++letter)
			{
				transitions += DFAStateArr[stateNum]->listLabels() + ", ";
				transitions += alphabetArr[letter];
				transitions += " = " + DFAStateArr[DFATransArr[stateNum][letter]]->listLabels() + "\n";
			}
		}
	}
	cout << "OUTPUT" << endl;
	cout << "States: \t\t" << stateDefLine << endl 
		<< "Alphabet: \t\t" << alphabetLine << endl 
		<< "Starting State: \t" << startStateLine << endl 
		<< "Accept States: \t\t" << acceptStateLine << endl << "Transitions: \n" << transitions;
	ofstream ofs;
	fileName += ".DFA";
	ofs.open(fileName.c_str());
	ofs << stateDefLine << endl << alphabetLine << endl << startStateLine << endl << acceptStateLine << endl << transitions;
	ofs.close();

}

State* NFA::epsClosure(State* firstState)
{	//Returns a state labeled with all labels which can be reached from the passed state, moving across epsilon paths.
	State* newState = new State();
	newState->combineWithState(firstState);
	int stateArrayPosition = (*(statePositions->find(firstState->labels->front()))).second;
	epsCloseRecursive(newState, stateArrayPosition);
	return newState;
}

void NFA::epsCloseRecursive(State* newState, int stateArrPos)
{
	int epsArrPos = (*(letterPositions->find(EPS))).second;
	list<int>::iterator iter = transitions[stateArrPos][epsArrPos].begin(),
						end = transitions[stateArrPos][epsArrPos].end();
	while(iter != end)
	{
		if(!newState->hasLabel(stateArr[*iter]->labels->front()))
			newState->combineWithState(stateArr[*iter]);
		else
			break;
		if(*iter != stateArrPos)
			epsCloseRecursive(newState, *iter);
		iter++;
	}
}

string NFA::sanitize(string input)
{
	int size = input.length(), start = 0, end = size - 1;
	const char* cstr = input.c_str();
	for(int i = 0; i < size; ++i)
	{
		if(cstr[i] != ' ')
		{
			break;
		}
		start = i;
	}
	for(int j = end; j > start; --j)
	{
		if(cstr[j] != ' ')
		{
			break;
		}
		end = j;
	}
	return input.substr(start, end-start);
}

string* NFA::splitTransitionLine(string line)
{
	string* toReturn = new string[3];
	const char* chars = line.c_str();
	if((int)chars[line.length() - 1] == 13)
		line = line.substr(0, line.length() - 1);
	int i = 0;
	while(i < line.length())
	{
		if(chars[i] == ',') break;
		i++;
	}
	if(i < line.length())
	{
		toReturn[0] = line.substr(0, i);
		i += 2;	//move i past the comma and space
		int j = 0;
		while(i + j < line.length())
		{
			if(chars[i+j] == '=') break;
			j++;
		}
		if(i + j < line.length())
		{
			toReturn[1] = line.substr(i, j - 1);
							//Reduce length by 1 to move by the space
			toReturn[2] = line.substr(i + j + 2);
		}					//Go to the end of the string, from 2 past the end of the last string.
	}
	for(int i = 0; i < 3; ++i)
	{
		toReturn[i] = sanitize(toReturn[i]);
	}
	return toReturn;
}
